package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

import java.util.ArrayList;
import java.util.List;

/**
 * LCA in bst
 * https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
 * 不用bst see 235 236
 *
 * TODO, 这个写法也有点呆了, 直接BST搜两个元素即可
 * https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/solution/
 *
 * @author tzp
 * @since 2020/9/14
 */
public class LC235 implements TreeProblem {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;

        List<TreeNode> search1 = search(root, p.val);
        List<TreeNode> search2 = search(root, q.val);
        if (search1 != null && search2 != null) {
            int i = 0;
            for (; i < search1.size(); i++) {
                if (i >= search2.size()) {
                    break;
                }
                if (search1.get(i).equals(search2.get(i))) {
                    continue;
                } else {
                    break;
                }
            }
            return search1.get(i - 1);
        } else {

            return null;
        }
    }

    public static List<TreeNode> search(TreeNode root, int v) {
        List<TreeNode> result = new ArrayList<>();
        TreeNode current = root;
        while (current != null) {
            if (current.val == v) {
                result.add(current);
                return result;
            } else if (current.val > v) {
                result.add(current);
                current = current.left;
            } else {
                result.add(current);
                current = current.right;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        Integer[] a = {6, 2, 8, 0, 4, 7, 9, null, null, 3, 5};
        TreeNode node = TreeNode.arrayToTreeNode(a);
//        System.out.println(search(node, 2));
//        System.out.println(search(node, 8));
//        System.out.println(search(node, 4));
        System.out.println(new LC235().lowestCommonAncestor(node, new TreeNode(2), new TreeNode(8)));
        System.out.println(new LC235().lowestCommonAncestor(node, new TreeNode(2), new TreeNode(4)));
        System.out.println(new LC235().lowestCommonAncestor(node, new TreeNode(2), new TreeNode(5)));
    }
}
